package class05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 最大的快乐值问题
 */
public class Code03_MaxHappy {

	/**
	 * 用数组表示图的方式 ---- 没有生成整棵树
	 * @param matrix
	 * @return
	 */
	// matrix 第一维度表示直接上级， 第二维度表示该员工的欢乐值
	// matrix.length 表示员工的数量
	public static int maxHappy(int[][] matrix) {
		// dp 横轴表示员工编号，纵轴表示是否参加
		int[][] dp = new int[matrix.length][2];
		boolean[] visited = new boolean[matrix.length];
		int root = 0;
		for (int i = 0; i < matrix.length; i++) {
			if (i == matrix[i][0]) {
				root = i;
			}
		}
		process(matrix, dp, visited, root);
		return Math.max(dp[root][0], dp[root][1]);
	}


	public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root) {
		visited[root] = true;
		dp[root][1] = matrix[root][1];
		for (int i = 0; i < matrix.length; i++) {
			if (matrix[i][0] == root && !visited[i]) {
				process(matrix, dp, visited, i);
				dp[root][1] += dp[i][0];
				dp[root][0] += Math.max(dp[i][1], dp[i][0]);
			}
		}
	}


	/**
	 * 方式二：树形DP ---- 生成了整棵树
	 */
	public static class Employee {
		public int happy; // 这名员工可以带来的快乐值
		List<Employee> subordinates; // 这名员工有哪些直接下级

		public Employee(int happy, List<Employee> subordinates) {
			this.happy = happy;
			this.subordinates = subordinates;
		}
	}

	public static int maxHappyDP(Employee boss) {
		if (boss == null) {
			return 0;
		}
		Info headInfo = process(boss);
		return Math.max(headInfo.laiMaxHappy, headInfo.buMaxHappy);
	}

	// 返回值结构
	public static class Info {
		public int laiMaxHappy; // 头结点来的情况下的最大快乐值
		public int buMaxHappy; // 头结点不来的情况下的最大快乐值
		public Info(int laiMaxHappy, int buMaxHappy) {
			this.laiMaxHappy = laiMaxHappy;
			this.buMaxHappy = buMaxHappy;
		}
	}


	// 递归过程，以x为头结点时他来不来的最大快乐值
	public static Info process(Employee x) {
		// base case
		if(x.subordinates==null || x.subordinates.isEmpty()) { // x是基层员工的时候。 来的话，快乐值就是他自己的；不来就是0
			return new Info(x.happy,0);
		}

		// 普通情况
		int lai = x.happy; // x来的情况下的最大快乐值，初始要算上x的
		int bu = 0; // x来的情况下的最大快乐值，初始值为0
		/** 本题是多叉树，所以使用了for循环去获取每个子树的信息 */
		for (Employee next : x.subordinates) {
			Info nextInfo = process(next);
			lai += nextInfo.buMaxHappy;
			bu += Math.max( nextInfo.laiMaxHappy, nextInfo.buMaxHappy );
		} // nextInfo.buMaxHappy 对应第二步获取子树的信息； += 对应第四步可能性的整合

		return new Info(lai, bu);
	}



	// for test
	public static void main(String[] args) {
		// 用数组表示图的方法
		int[][] matrix = { { 1, 8 }, { 1, 9 }, { 1, 10 } };
		System.out.println(maxHappy(matrix));

		// 树形DP
		Employee employee0 = new Employee(8, null);
		Employee employee2 = new Employee(10, null);
		Employee employee1 = new Employee(9, Arrays.asList(employee0, employee2));
		System.out.println(maxHappyDP(employee1));
	}
}
